package dsg

import (
	"io"
	"fmt"
)

type LinkMat struct {
	size int
	row_ls [](*LinkSet)
	col_ls [](*LinkSet)
	crow int
	ccol int
}

func InitLinkMat (size int) * LinkMat {
	var lm LinkMat
	lm.size = size
	lm.row_ls = make ([](*LinkSet), size)
	lm.col_ls = make ([](*LinkSet), size)
	for i := 0; i < size; i ++ {
		lm.row_ls[i] = InitLinkSet (size)
		lm.col_ls[i] = InitLinkSet (size)
	}
	lm.crow = -1
	lm.ccol = -1
	return &lm
}

func InverseLinkMat (lm * LinkMat) (lm1 * LinkMat) {
	size := lm.size
	lm1 = InitLinkMat(size)
	for row := 0; row < size; row ++ {
		for col := 0; col < size; col ++ {
			if !lm.GetLabel (row, col) {
				lm1.Set (row, col)
			}
		}
	}
	return 
}

func (lm * LinkMat) Expand (size int) {
	for i := 0; i < lm.size; i ++ {
		lm.row_ls[i].Expand (size)
		lm.col_ls[i].Expand (size) 
	}
	for i := 0; i < size; i ++ {
		new_rls := InitLinkSet (lm.size + size)
		lm.row_ls = append (lm.row_ls, new_rls)
		new_cls := InitLinkSet (lm.size + size)
		lm.col_ls = append (lm.col_ls, new_cls)
	}
	lm.size += size
}

func (lm * LinkMat) Set (row int, col int) {
	lm.row_ls[row].Set (col)
	lm.col_ls[col].Set (row)
}

func (lm * LinkMat) UnSet (row int, col int) {
	lm.row_ls[row].UnSet (col)
	lm.col_ls[col].UnSet (row)
}

func (lm * LinkMat) Clear () {
	for i := 0; i < lm.size; i ++ {
		lm.row_ls[i].Clear()
		lm.col_ls[i].Clear()
	}
	lm.crow = -1
	lm.ccol = -1
}

func (lm * LinkMat) ClearRow (row int) {
      ls := lm.row_ls[row]
      for ls.TraverseStart(); ls.GetTraverseLabel() != -1; ls.TraverseForward() {
            col := ls.GetTraverseLabel()
            lm.col_ls[col].UnSet (row)
      }
      ls.Clear()
}

func (lm * LinkMat) ClearCol (col int) {
      ls := lm.col_ls[col]
      for ls.TraverseStart(); ls.GetTraverseLabel() != -1; ls.TraverseForward() {
            row := ls.GetTraverseLabel()
            lm.row_ls[row].UnSet (col)
      }
      ls.Clear()
}

func (lm * LinkMat) GetSize () int {
	return lm.size
}

func (lm * LinkMat) GetRowNum (row int) int {
	return lm.row_ls[row].GetNum ()
}

func (lm * LinkMat) GetColNum (col int) int {
	return lm.col_ls[col].GetNum ()
}

func (lm * LinkMat) GetNum () int {
	num := 0
	for i := 0; i < lm.size; i ++ {
		num += lm.GetRowNum(i)
	}
	return num
}

func (lm * LinkMat) GetLabel (row, col int) bool {
	return lm.row_ls[row].GetLabel (col)
}

func (lm * LinkMat) RowTraverseStart (row int) {
	lm.crow = row
	lm.row_ls[row].TraverseStart ()
}

func (lm * LinkMat) RowTraverseForward () {
	if lm.crow < 0 || lm.crow >= lm.size { return }
	lm.row_ls[lm.crow].TraverseForward ()
}

// col = -1 if traverse to tail
func (lm * LinkMat) GetRowTraverseLabel () (row, col int) {
	if lm.crow < 0 || lm.crow >= lm.size { return -1, -1 }
	row = lm.crow
	col = lm.row_ls[lm.crow].GetTraverseLabel()
	return 
}

func (lm * LinkMat) ColTraverseStart (col int) {
	lm.ccol = col
	lm.col_ls[col].TraverseStart ()
}

func (lm * LinkMat) ColTraverseForward () {
	if lm.ccol < 0 || lm.ccol >= lm.size { return }
	lm.col_ls[lm.ccol].TraverseForward ()
}

// row = -1 if traverse to tail
func (lm * LinkMat) GetColTraverseLabel () (row, col int) {
	if lm.ccol < 0 || lm.ccol >= lm.size { return -1, -1 }
	row = lm.col_ls[lm.ccol].GetTraverseLabel()
	col = lm.ccol
	return 
}

func (lm * LinkMat) TraverseStart () {
	lm.crow = 0
	for i := 0; i < lm.size; i ++ {
		lm.row_ls[i].TraverseStart ()
	}

	for ; lm.crow < lm.size && lm.row_ls[lm.crow].GetTraverseLabel() == -1 ; lm.crow ++ {}
}

func (lm * LinkMat) TraverseForward () {
	if lm.crow < 0 || lm.crow >= lm.size { return }
	lm.row_ls[lm.crow].TraverseForward()
	for ; lm.crow < lm.size && lm.row_ls[lm.crow].GetTraverseLabel() == -1 ; lm.crow ++ {}
}

// return -1, -1 if traverse to tail
func (lm * LinkMat) GetTraverseLabel () (row, col int) {
	return lm.GetRowTraverseLabel ()
}

func (lm * LinkMat) GetRow (row int) []int {
      res := make ([]int, 0)
      
      for lm.RowTraverseStart (row) ;; lm.RowTraverseForward() {
            _, col := lm.GetRowTraverseLabel()
            if col == -1 {break}
            res = append (res, col)
      }
      return res
}

func (lm * LinkMat) GetCol (col int) []int {
      res := make ([]int, 0)
      
      for lm.ColTraverseStart (col) ;; lm.ColTraverseForward() {
            row, _ := lm.GetColTraverseLabel()
            if row == -1 {break}
            res = append (res, row)
      }
      return res
}

func (lm * LinkMat) GetAllLabel () [][]int {
      res := make ([][]int, 0)

      for lm.TraverseStart () ;; lm.TraverseForward() {
            row, col := lm.GetTraverseLabel()
            if row == -1 || col == -1 {break}
            res = append (res, []int{row, col})
      }
      return res

}

func (lm * LinkMat) Save (fout io.Writer) {
	fmt.Fprintf (fout, "%d %d\n", lm.size, lm.GetNum())
	for lm.TraverseStart () ;; lm.TraverseForward() {
		row, col := lm.GetTraverseLabel()
		if row == -1 || col == -1 {break}
		fmt.Fprintf (fout, "%d %d\n", row, col)
	}
}

func LoadLinkMat (fin io.Reader)  * LinkMat {
	var size, num int
	n, _ := fmt.Fscan (fin, &size, &num)
	if n != 2 {return nil}

	lm := InitLinkMat (size)
	for i := 0; i < num; i ++ {
		var row, col int
		fmt.Fscan (fin, &row, &col)
		lm.Set (row, col)
	}

	return lm
}

